package recursion;

public class Queen8 {

    int numOfQueens = 8;
    int[] result = new int[numOfQueens]; // 解的表示，下标表示行，值表示列
    static int count = 0;

    public static void main(String[] args) {
        Queen8 q = new Queen8();
        q.placeQueen(0);
        System.out.printf("共有 %d 种解法", count);
    }

    // 放置第n个皇后
    private void placeQueen(int n) {
        // 能进入这个if，说明所有皇后的位置都不冲突，最终执行了placeQueen(7+1)，这就是退出递归的条件
        if (n == numOfQueens) {
            count++;
            show();
            return;
        }
        // 每一个placeQueen里都会有一个for，递归实现了for的嵌套
        for (int i = 0; i < numOfQueens; i++) {
            result[n] = i;
            if (!isConflict(n)) {
                placeQueen(n + 1);
            }
        }
    }

    // 判断第n个皇后的位置是否可行
    private boolean isConflict(int n) {
        for (int i = 0; i < n; i++) {
            // 第一个条件判断是否在同一列
            // 第二个条件判断是否在同一斜线。思路是将result还原为二维的棋盘，然后看是否abs(Δy / Δx) == 1
            if (result[i] == result[n] || Math.abs(n - i) == Math.abs(result[n] - result[i])) {
                return true;
            }
        }
        return false;
    }

    // 输出当前结果
    private void show() {
        for (int i = 0; i < numOfQueens; i++) {
            System.out.print(result[i] + "  ");
        }
        System.out.println();
    }
}
